#include "main/utils.h"
using namespace std;

vector<string> getNeighbors(string cur,
                            vector<string> words) {
  auto isNeighbor = [&](string word2) {
    int diff = 0;
    for (int i = 0; i < cur.size(); ++i) {
      if (cur[i] != word2[i]) {
        ++diff;
      }
      if (diff > 1) {
        return false;
      }
    }
    if (diff == 1) {
      return true;
    }
    return false;
  };

  vector<string> ret;
  for (int i = 0; i < words.size(); ++i) {
    if (isNeighbor(words[i])) {
      ret.push_back(words[i]);
    }
  }
  return ret;
}

int ladderLength1(const string& begin_word,
                  const string& end_word,
                  const vector<string>& words) {
  queue<string> queue1;
  queue<string> queue2;
  set<string> not_visited(words.begin(), words.end());
  queue1.push(begin_word);
  int length = 1;
  while (!queue1.empty()) {
    string cur = queue1.front();
    queue1.pop();
    if (cur == end_word) {
      return length;
    }
    auto neighbors = getNeighbors(cur, words);
    for (auto neighbor : neighbors) {
      if (not_visited.find(neighbor) != not_visited.end()) {
        queue2.push(neighbor);
        not_visited.erase(neighbor);
      }
    }
    if (queue1.empty()) {
      ++length;
      swap(queue1, queue2);
    }
  }
  return 0;
}

int ladderLength2(const string& begin_word,
                  const string& end_word,
                  const vector<string>& words) {
  set<string> not_visited(words.begin(), words.end());
  if (not_visited.find(end_word) == not_visited.end()) {
    return 0;
  }

  int length = 2;
  set<string> set1, set2;
  set1.insert(begin_word);
  set2.insert(end_word);
  while (!set1.empty() && !set2.empty()) {
    if (set2.size() < set1.size()) {
      swap(set2, set1);
    }
    set<string> set3;
    for (string word : set1) {
      auto neighbors = getNeighbors(word, words);
      for (auto neighbor : neighbors) {
        if (set2.find(neighbor) != set2.end()) {
          return length;
        }
        if (not_visited.find(neighbor) != not_visited.end()) {
          set3.insert(neighbor);
          not_visited.erase(neighbor);
        }
      }
    }
    set1 = set3;
    ++length;
  }
  return 0;
}

int main() {
  string begin_word = "hit";
  string end_word = "cog";
  vector<string> words = {"hot", "dot", "dog", "lot", "log", "cog"};
  cout << ladderLength1(begin_word, end_word, words) << endl;
  cout << ladderLength2(begin_word, end_word, words) << endl;

  return 0;
}
